package com.zhugang.week13.sorting;

/**
 * @program algorithms
 * @description: bubbleSort
 * @author: chanzhugang
 * @create: 2022/09/30 22:58
 */
public class BubbleSort implements IMutableSorter {

    /**
     * 冒泡排序：每次把最大值交换到最后面
     * O(n^2)
     *
     * @param A
     */
    @Override
    public void sort(int[] A) {
        for (int i = A.length - 1; i >= 0; i--) {
            // 0 - i 之间把最大值放在A[i] 中
            bubble(A, 0, i + 1);
        }
    }

    private void bubble(int[] A, int i, int j) {
        // 比较相邻元素，交换位置
        for (int k = 0; k < j - 1; k++) {
            if (A[k] > A[k + 1]) {
                swap(A, k, k + 1);
            }
        }
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}